package hadoop.mr;

/**
 * 归并排序(递归方式)
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] data = {50,10,90,30,70,40,80,60,20};
        print(data,true);
        mergeSort(data, 0, data.length -1 );
        print(data,false);
    }

    private static void mergeSort(int[] data, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;
            mergeSort(data, left, middle);
            mergeSort(data, middle + 1, right);
            merge(data, left, middle, right);
        }

    }

    private static void merge(int[] data, int left, int middle, int right) {
        int[] tmpArray = new int[data.length];
        int mid = middle + 1;
        int third = left;
        int tmp = left;

        while(left <= middle && mid <= right) {

            if(data[left] <= data[mid]) {
                tmpArray[third++] = data[left++];
            }else {
                tmpArray[third++] = data[mid++];
            }
        }

        // 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）
        while (mid <= right) {
            tmpArray[third++] = data[mid++];
        }
        while (left <= middle) {
            tmpArray[third++] = data[left++];
        }

        // 将临时数组中的内容拷贝回原数组中
        // （原left-right范围的内容被复制回原数组）
        while (tmp <= right) {
            data[tmp] = tmpArray[tmp++];
        }

    }

    private static void print(int[] data, boolean before) {
        if(before) {
            System.out.println("排序之前：");
        }else {
            System.out.println("排序之后：");
        }
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + ", ");
        }
        System.out.println();
    }
}
